﻿#include "pch.h"
#include "CppUnitTest.h"

#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

template<class ELE, class ResultType>
class IUpperDPCall
{
public:
	virtual void OnEnum(int n,vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount) = 0;
	virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp) = 0;
};

template<class ELE, class ResultType>
class CUperrDP
{
public:
	CUperrDP(int iCustomStatusCount, IUpperDPCall<ELE, ResultType>& call, ELE minEle, ELE maxEle)
		:m_iCustomStatusCount(iCustomStatusCount),m_call(call),m_minEle(minEle),m_maxEle(maxEle)
	{
	}
	void Init(const ELE* pHigh, int iEleCount)
	{
		m_vDP.assign(iEleCount + 1, vector<ResultType>(m_iCustomStatusCount));
		m_vDpUpper = m_vDP;
		m_call.OnInitEnd(m_vDP.back(), m_vDpUpper.back());
		//预处理增加的一位
		for (int i = iEleCount - 1;i > 0;i--) {
			m_call.OnEnum(i,m_vDpUpper[i], m_vDpUpper[i + 1], pHigh[i],m_iCustomStatusCount);
			for (auto j = m_minEle; j < pHigh[i];j++) {
				m_call.OnEnum(i,m_vDpUpper[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
			for (auto j = m_minEle; j <= m_maxEle;j++) {
				m_call.OnEnum(i,m_vDP[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
		}
		m_call.OnEnum(0,m_vDpUpper[0], m_vDpUpper[1], pHigh[0], m_iCustomStatusCount);
		for (auto j = m_minEle; j < pHigh[0];j++) {
			m_call.OnEnum(0,m_vDP[0], m_vDP[1], j, m_iCustomStatusCount);
		}
	}
	ResultType Sum(int iMinCustomStatu, int iMaxCustomStatu) {
		ResultType ret = 0;
		for (int i = iMinCustomStatu; i <= iMaxCustomStatu;i++) {
			ret += m_vDP[0][i] + m_vDpUpper[0][i];
		}
		return ret;
	}
	ResultType Sum() {
		return Sum(0, m_iCustomStatusCount - 1);
	}
	vector<vector<ResultType>> m_vDP, m_vDpUpper;
	const ELE m_minEle, m_maxEle;
protected:
	const int m_iCustomStatusCount;
	IUpperDPCall<ELE, ResultType>& m_call;
};

template<class ELE, class ResultType>
class CUperrDP2
{
public:
	CUperrDP2(int iCustomStatusCount, IUpperDPCall<ELE, ResultType>& call, ELE minEle, ELE maxEle, ELE firstMinEle) 
		:m_iCustomStatusCount(iCustomStatusCount), m_call(call), m_minEle(minEle),m_maxEle(maxEle),m_firstMinEle(firstMinEle)
	{
	}
	void Init(const ELE* pHigh, int iEleCount)
	{
		m_vDP.assign(iEleCount + 1, vector<ResultType>(m_iCustomStatusCount));
		m_vDpUpper = m_vDP;
		m_vFirstDP = m_vDP;
		m_call.OnInitEnd(m_vDP.back(), m_vDpUpper.back());
		//预处理增加的一位
		for (int i = iEleCount - 1;i > 0;i--) {
			m_call.OnEnum(i,m_vDpUpper[i], m_vDpUpper[i + 1], pHigh[i], m_iCustomStatusCount);
			for (auto j = m_minEle; j < pHigh[i];j++) {
				m_call.OnEnum(i,m_vDpUpper[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
			for (auto j = m_minEle; j <= m_maxEle;j++) {
				m_call.OnEnum(i,m_vDP[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
			for (auto j = m_firstMinEle; j <= m_maxEle;j++) {
				m_call.OnEnum(i,m_vFirstDP[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
		}
		m_call.OnEnum(0,m_vFirstDP[0], m_vDpUpper[1], pHigh[0], m_iCustomStatusCount);
		for (auto j = m_firstMinEle; j < pHigh[0];j++) {
			m_call.OnEnum(0,m_vFirstDP[0], m_vDP[1], j, m_iCustomStatusCount);
		}
	}
	ResultType Sum(int iMinCustomStatu, int iMaxCustomStatu) {
		ResultType ret = 0;
		for (int i = 0;i + 1 < m_vFirstDP.size();i++) {
			ret += accumulate(m_vFirstDP[i].begin() + iMinCustomStatu, m_vFirstDP[i].begin() + iMaxCustomStatu + 1, (ResultType)0);
		}
		return ret;
	}
	ResultType Sum() {
		return Sum(0, m_iCustomStatusCount - 1);
	}
	vector<vector<ResultType>> m_vDP, m_vDpUpper,m_vFirstDP;
	ELE m_minEle, m_maxEle, m_firstMinEle;
protected:
	const int m_iCustomStatusCount;
	IUpperDPCall<ELE, ResultType>& m_call;
};


namespace DigitDPLC
{
	TEST_CLASS(LC2376)
	{
	public:
		//LC2376. 统计特殊整数
		template<class ELE, class ResultType>
		class CCall: public IUpperDPCall<ELE,ResultType>
		{
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n,vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				for (int i = 0; i < iCustomStatusCount;i++) {
					if ((1 << cur) & i) { continue; }
					dp[(1 << cur) | i] += vNext[i];
				}
			}
		};

		class Solution {
		public:
			int countSpecialNumbers(int n) {
				string str = to_string(n);
				const int len = str.length();
				CCall<char, int> call;
				CUperrDP2<char, int > dp(1024,call, '0', '9', '1');
				dp.Init(str.c_str(), len);
				int ans = dp.Sum(0,1023);				
				return ans;
			}
		};
		int n;
		TEST_METHOD(TestMethod11)
		{
			n = 20;
			auto res = Solution().countSpecialNumbers(n);
			AssertEx(19, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 5;
			auto res = Solution().countSpecialNumbers(n);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod13)
		{
			n = 135;
			auto res = Solution().countSpecialNumbers(n);
			AssertEx(110, res);
		}
		TEST_METHOD(TestMethod14)
		{
			n = 9;
			auto res = Solution().countSpecialNumbers(n);
			AssertEx(9, res);
		}
		TEST_METHOD(TestMethod15)
		{
			n = 99;
			auto res = Solution().countSpecialNumbers(n);
			AssertEx(90, res);
		}
		TEST_METHOD(TestMethod16)
		{
			n = 999;
			auto res = Solution().countSpecialNumbers(n);
			AssertEx(738, res);
		}
		TEST_METHOD(TestMethod17)
		{
			n = 9999;
			auto res = Solution().countSpecialNumbers(n);
			AssertEx(5274, res);
		}
		TEST_METHOD(TestMethod19)
		{
			n = 2'000'000'000;
			auto res = Solution().countSpecialNumbers(n);
			AssertEx(5974650, res);
		}
	};
	TEST_CLASS(LC1012)
	{
	public:
		//【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字
		template<class ELE, class ResultType>
		class CCall : public IUpperDPCall<ELE, ResultType>
		{
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				for (int i = 0; i < iCustomStatusCount;i++) {
					if ((1 << cur) & i) { continue; }
					dp[(1 << cur) | i] += vNext[i];
				}
			}
		};
		class Solution {
		public:
			int numDupDigitsAtMostN(int n) {
				string str = to_string(n);
				const int len = str.length();
				CCall<char, int> call;
				CUperrDP2<char, int > dp(1024, call, '0', '9', '1');
				dp.Init(str.c_str(), len);
				int ans = dp.Sum(0, 1023);
				return n - ans;
			}
		};
		int n;
		TEST_METHOD(TestMethod11)
		{
			Solution sln;
			n = 20;
			auto res = sln.numDupDigitsAtMostN(n);
			AssertEx(res, 1);
		}
		TEST_METHOD(TestMethod12)
		{
			Solution sln;
			n = 100;
			auto res = sln.numDupDigitsAtMostN(n);
			AssertEx(res, 10);
		}
		TEST_METHOD(TestMethod13)
		{
			Solution sln;
			n = 1000;
			auto res = sln.numDupDigitsAtMostN(n);
			AssertEx(res, 262);
		}
	};
	TEST_CLASS(LC2801)
	{
	public:
		//LC2801. 统计范围内的步进数字数目
		template<class ELE, class ResultType>
		class CCall : public IUpperDPCall<ELE, ResultType>
		{
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp[10] = upDp[10] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				dp[cur] += vNext[10];
				if (cur) {
					dp[cur] += vNext[cur - 1];
				}
				if (cur + 1 < 10) {
					dp[cur] += vNext[cur + 1];
				}
			}
		};
		class Solution {
		public:
			int countSteppingNumbers(string low, string high) {
				CCall<char,C1097Int<>> call;
				CUperrDP2<char, C1097Int<>> dp1(11,call, '0', '9', '1'), dp2(11, call, '0', '9', '1');
				dp1.Init(low.c_str(), low.length());
				dp2.Init(high.c_str(), high.length());
				C1097Int<> ans = dp2.Sum()-dp1.Sum();
				bool is = true;
				for (int i = 1; i < low.length();i++) {
					if (1 != abs(low[i] - low[i - 1])) { is = false; }
				}
				return (ans + is).ToInt();
			}
		};
		string low,  high;
		TEST_METHOD(TestMethod11)
		{
			low = "1", high = "11";
			auto res = Solution().countSteppingNumbers(low, high);
			AssertEx(10, res);
		}
		TEST_METHOD(TestMethod12)
		{
			low = "90", high = "101";
			auto res = Solution().countSteppingNumbers(low, high);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			low = "106", high = "121";
			auto res = Solution().countSteppingNumbers(low, high);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod14)
		{
			low = "1", high = "90";
			auto res = Solution().countSteppingNumbers(low, high);
			AssertEx(25, res);
		}
		TEST_METHOD(TestMethod15)
		{
			low = "1", high = "98";
			auto res = Solution().countSteppingNumbers(low, high);
			AssertEx(26, res);
		}
		TEST_METHOD(TestMethod16)
		{
			low = "1", high = "101";
			auto res = Solution().countSteppingNumbers(low, high);
			AssertEx(27, res);
		}
		TEST_METHOD(TestMethod17)
		{
			low = "1", high = "10000000000000000000000000000000000000000000";
			auto res = Solution().countSteppingNumbers(low, high);
			AssertEx(28960639, res);
		}
		
	};	
	TEST_CLASS(LC2719)
	{
	public:
		//【C++算法】【数位dp】【动态规划】2719统计整数数目
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE,ResultType>
		{
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue,int iCustomStatusCount)
			{
				for (int i = 0; i + curValue - '0' < iCustomStatusCount;i++) {
					dp[i + curValue - '0'] += vNext[i];
				}
			}
		};

		class Solution {
		public:
			int count(string num1, string num2, int min_sum, int max_sum) {
				CCall<char, C1097Int<>> call;
				CUperrDP<char,C1097Int<>> dp1(max_sum + 1,call, '0', '9'), dp2(max_sum + 1,call, '0', '9');
				dp1.Init(num1.c_str(), num1.length());
				dp2.Init(num2.c_str(), num2.length());
				auto ans = dp2.Sum(min_sum, max_sum)-dp1.Sum(min_sum, max_sum);
				int sum = 0;
				for (const auto& ch : num1) {
					sum += ch - '0';
				}
				ans += ((min_sum <= sum) && (sum <= max_sum));
				return ans.ToInt();
			}
		};
		TEST_METHOD(TestMethod01)
		{
			int res = 0;
			res = Solution().count("0", "9", 0, 100);
			AssertEx(10, res);
		}
		TEST_METHOD(TestMethod11)
		{
			int res = 0;
			res = Solution().count("2", "5", 0, 100);
			AssertEx(4,res);
			res = Solution().count("12", "15", 0, 100);
			AssertEx(4, res);
			res = Solution().count("112", "115", 0, 100);
			AssertEx(4, res);
			res = Solution().count("112", "115", 5, 100);
			AssertEx(3, res);
			res = Solution().count("112", "115", 0, 6);
			AssertEx(3, res);
			res = Solution().count("112", "115", 5, 6);
			AssertEx(2, res);
			res = Solution().count("1", "12", 1, 8);
			AssertEx(11, res);
		}
		TEST_METHOD(TestMethod12)
		{
			int res = 0;
			res = Solution().count("1", "10000000000000000000", 100, 400);
			AssertEx(183161420, res);
		}
	};
	TEST_CLASS(LC600)
	{
	public:
		//【C++ 数位dp】600. 不含连续1的非负整数
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				dp[cur] += vNext[0];
				if (0 == cur) {
					dp[cur] += vNext[1];
				}
			}
		};
		class Solution {
		public:
			int findIntegers(int n) {
				string strN;
				while (n > 0)
				{
					strN += ((n & 1) ? "1" : "0");
					n /= 2;
				}
				std::reverse(strN.begin(), strN.end());
				const int len = strN.length();
				CCall<char, int> call;
				CUperrDP<char, int> dp(2, call, '0', '1');
				dp.Init(strN.c_str(), strN.length());
				return dp.Sum() ;
			}
		};
		int n;
		TEST_METHOD(TestMethod01)
		{
			Solution sln;
			n = 5;
			auto res = sln.findIntegers(n);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod11)
		{
			Solution sln;
			n = 1;
			auto res = sln.findIntegers(n);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			Solution sln;
			n = 2;
			auto res = sln.findIntegers(n);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			Solution sln;
			n = 10;
			auto res = sln.findIntegers(n);
			AssertEx(8, res);
		}
		TEST_METHOD(TestMethod14)
		{
			Solution sln;
			n = 100;
			auto res = sln.findIntegers(n);
			AssertEx(34, res);
		}
		TEST_METHOD(TestMethod15)
		{
			Solution sln;
			n = 1000000000;
			auto res = sln.findIntegers(n);
			AssertEx(2178309, res);
		}
	};
	TEST_CLASS(LC3519)
	{
	public:
		//【数位dp】3519. 统计逐位非递减的整数|2246
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
			virtual void OnInitEnd( vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp.back()=upDp.back() = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				for (int i = cur; i< iCustomStatusCount;i++) {
					dp[cur] += vNext[i];
				}
			}
		};
		class Solution {
		public:
			int countNumbers(string left, string r, int b) {
				string str1 = ToB(left,b);
				string str2 = ToB(r, b);
				CCall<char, C1097Int<>> call;
				CUperrDP<char, C1097Int<>> dp1(b, call, '0', '0' + b - 1), dp2(b, call, '0', '0' + b - 1);
				dp1.Init(str1.c_str(), str1.length());
				dp2.Init(str2.c_str(), str2.length());
				bool is = true;
				for (int i = 1;i < str1.length();i++) {
					if (str1[i - 1] > str1[i]) { is = false; }
				}
				auto ans = dp2.Sum() - dp1.Sum() + is;				
				return ans.ToInt();
			}
			string ToB(const string& str, int b) {
				bigint b1(str);
				string str2;
				while (b1 > 0) {
					int x = b1 % b;
					str2 += x + '0';
					b1 = b1 / b;
				}
				if ("" == str2) { str2 = "0"; }
				return string(str2.rbegin(),str2.rend());
			}
		};
		TEST_METHOD(TestMethod01)
		{
			Solution sln;		
			auto res = sln.countNumbers("23", "28",8);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod11)
		{
			Solution sln;
			auto res = sln.countNumbers("2", "7",2);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			Solution sln;
			auto res = sln.countNumbers("1", "1000000000000", 8);
			AssertEx(104637, res);
		}
	};
	TEST_CLASS(LC2827)
	{
	public:
		//【动态规划 数位dp】2827. 范围中美丽整数的数目|2324
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
		public:
			CCall(int k):m_iK(k) {}
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				const int inx = m_iK * 10 + 0;
				dp[inx] = upDp[inx] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				for (int pre = 0; pre < iCustomStatusCount;pre++) {
					int i1 = pre / m_iK, i2 = pre % m_iK;
					if (cur & 1) {
						i1++;
					}
					else {
						i1--;
					}
					if ((i1 < 0) || (i1 > 19)) { continue; }
					i2 = (10*i2+cur) % m_iK;
					dp[pre] += vNext[m_iK * i1 + i2];
				}
			}
			int m_iK;
		};
		class Solution {
		public:
			int numberOfBeautifulIntegers(int low, int high, int k) {
				CCall<char, int> call(k);
				CUperrDP2<char, int> dp1(20 * k, call, '0', '9', '1'), dp2(20 * k, call, '0', '9', '1');
				string str1 = to_string(low);
				string str2 = to_string(high);
				dp1.Init(str1.c_str(), str1.length());
				dp2.Init(str2.c_str(), str2.length());
				int cnt = 0;
				for (int tmp = low; tmp;tmp /= 10) {
					if ((tmp % 10) & 1) { cnt++; }
					else {
						cnt--;
					}
				}
				bool is = (0 == cnt) && (0 == low % k);
				const int inx = k * 10;
				const auto ans = dp2.Sum(inx, inx) - dp1.Sum(inx, inx)+ is;
				return ans;
			}
		};
		TEST_METHOD(TestMethod01)
		{
			Solution sln;
			auto res = sln.numberOfBeautifulIntegers(10, 20, 3);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod11)
		{
			Solution sln;
			auto res = sln.numberOfBeautifulIntegers(1, 10, 1);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			Solution sln;
			auto res = sln.numberOfBeautifulIntegers(5, 5, 2);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod13)
		{
			Solution sln;
			auto res = sln.numberOfBeautifulIntegers(1, 1000000000, 3);
			AssertEx(8298064, res);
		}
	};
	TEST_CLASS(LC2999)
	{
	public:
		//【数位dp】【数论】【动态规划】2999. 统计强大整数的数目|2351
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
		public:	
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{				
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				dp[0] += vNext[0];
			}
			int m_iK;
		};
		class Solution {
		public:
			long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
				m_limit = limit+'0';
				m_s = s;
				bool is = true;
				string str1 = to_string(start);
				const int len1 = str1.length() - s.length();
				if ((len1 < 0) || (str1.substr(len1) != s)) { is = false; }
				if(*max_element(str1.begin(),str1.end()) > m_limit) { is = false; }
				return f(to_string(finish))-f(to_string(start))+is;
			}
			long long g(string x) {
				CCall<char, long long> call;
				CUperrDP<char, long long> dp(1, call, '0', m_limit);
				dp.Init(x.c_str(), x.length());
				return dp.Sum();
			}
			long long f(string x) {
				const int len1 = x.length() - m_s.length();
				if (len1 < 0) { return 0; }
				if (0 == len1) { return x >= m_s; }		
				for (int i = 0;i < x.length();i++) {
					if (x[i] > m_limit) {
						for (int j = i;j < x.length();j++) {
							x[j] = m_limit;
						}
						break;
					}
				}
				string str1 = x.substr(0, len1);
				string str2 = x.substr(len1);				
				return g(str1)- 1 + (str2 >= m_s);
			}
			char m_limit;
			string m_s;
		};
		long long start = 1, finish = 6000, limit = 4;
		string s = "124";
		TEST_METHOD(TestMethod01)
		{
			start = 1, finish = 6000, limit = 4,s = "124";
			auto res = Solution().numberOfPowerfulInt(start, finish, limit, s);
			AssertEx(5LL, res);
		}
		TEST_METHOD(TestMethod11)
		{
			start = 15, finish = 215, limit = 6, s = "10";
			auto res = Solution().numberOfPowerfulInt(start, finish, limit, s);
			AssertEx(2LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			start = 1000, finish = 2000, limit = 4, s = "3000";
			auto res = Solution().numberOfPowerfulInt(start, finish, limit, s);
			AssertEx(0LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			start = 1, finish = 1000000000000, limit = 4, s = "124";
			auto res = Solution().numberOfPowerfulInt(start, finish, limit, s);
			AssertEx(1953125LL, res);
		}
	};
	TEST_CLASS(LC3352)
	{
		//【逆向思考】LC3352. 统计小于 N 的 K 可约简整数|2451
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
		public:
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				if ('0' == curValue) {
					for (int i = 0;i < iCustomStatusCount;i++) {
						dp[i] += vNext[i];
					}
				}
				else if ('1' == curValue) {
					for (int i = 1;i < iCustomStatusCount;i++) {
						dp[i] += vNext[i-1];
					}
				}	
			}
			int m_iK;
		};
		class Solution {
		public:
			int countKReducibleNumbers(string s, int K) {
				typedef C1097Int<> BI;
				const int N = s.length();
				vector<bool> pre(N + 1);
				pre[1] = true;
				CBitCounts bc(N + 1);
				for (int k = 1; k < K; k++) {
					auto cur = pre;
					for (int i = 0; i <= N; i++) {
						cur[i] = cur[i] || pre[bc.m_vCnt[i]];
					}
					pre.swap(cur);
				}
				const int cnt1 = count(s.begin(), s.end(), '1');
				BI ans = -pre[cnt1];
				CCall<char, C1097Int<>> call;
				CUperrDP<char, C1097Int<>> dp(N + 1, call, '0', '1');
				dp.Init(s.c_str(), s.length());
				
				for (int i = 0; i <= N; i++) {
					auto cur = dp.Sum(i, i);
					if (!pre[i]) { continue; }
					ans += cur;
				}
				return ans.ToInt();
			}
		};
		string s;
		int k;
		TEST_METHOD(TestMethod1)
		{
			s = "111", k = 1;
			auto res = Solution().countKReducibleNumbers(s, k);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod2)
		{
			s = "1000", k = 2;
			auto res = Solution().countKReducibleNumbers(s, k);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod3)
		{
			s = "1", k = 3;
			auto res = Solution().countKReducibleNumbers(s, k);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod4)
		{
			s = "111111111111111111111111111111111111111111111111111111111111111111111111111111101111", k = 5;
			auto res = Solution().countKReducibleNumbers(s, k);
			AssertEx(946258173, res);
		}
	};
	TEST_CLASS(LC1397)
	{
		//【数位dp】【动态规划】【KMP】1397. 找到所有好字符串
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
		public:
			CCall(const string& evil) {
				const int N = evil.length();
				m_vTo.assign(N, vector<int>(26));	
				auto next = KMP::Prefix‌LongestCommonPrefix‌(evil);
				for (int i = 0; i < N;i++) {
					for (int j = 0;j < 26;j++) {						
							
						int k = i;
						for (;k && (evil[k] != 'a' + j);k = next[k]);
						k += (evil[k] == 'a' + j);
						m_vTo[i][j] = k;
						assert(k == Tmp(evil, i, j + 'a'));
					}
				}	
			}
			int Tmp(const string& evil, int len, char ch) {				
				string s = evil.substr(0,len) + ch;
				for (int i = s.length();i > 0;i--) {
					if (s.substr(s.length() - i) == evil.substr(0, i)) { return i; }
				}
				return 0;
			}
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp.assign(dp.size(), 1);
				upDp.assign(upDp.size(), 1);
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int j = curValue - 'a';
				for (int i = 0;i < iCustomStatusCount;i++) {
					const int k = m_vTo[i][j];
					if (k >= iCustomStatusCount) { 
						continue; }
					dp[i] += vNext[k];
				}
			}
			vector<vector<int>> m_vTo;
			int m_iK;
		};
		class Solution {
		public:
			int findGoodStrings(int n, string s1, string s2, string evil) {
				CCall<char,C1097Int<>> call(evil);
				CUperrDP2<char, C1097Int<>> dp1(evil.length(), call, 'a', 'z','a'), dp2(evil.length(), call, 'a', 'z','a');
				dp1.Init(s1.c_str(),s1.length());
				dp2.Init(s2.c_str(),s2.length());
				auto ans = dp2.m_vFirstDP[0][0] - dp1.m_vFirstDP[0][0] + (-1 ==s1.find(evil));
				return ans.ToInt();
			}
		};
		int n;
		string s1, s2, evil;
		TEST_METHOD(TestMethod1)
		{			
			Solution sln;
			n = 2, s1 = "aa", s2 = "da", evil = "b";
			auto res = sln.findGoodStrings(n, s1, s2, evil);
			AssertEx(51, res);
		}
		TEST_METHOD(TestMethod2)
		{
			Solution sln;
			n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet";
			auto res = sln.findGoodStrings(n, s1, s2, evil);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod3)
		{
			Solution sln;
			n = 2, s1 = "gx", s2 = "gz", evil = "x";
			auto res = sln.findGoodStrings(n, s1, s2, evil);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod4)
		{
			Solution sln;
			n = 3, s1 = "aaa", s2 = "azz", evil = "sxx";
			auto res = sln.findGoodStrings(n, s1, s2, evil);
			AssertEx(26*26, res);
		}
		TEST_METHOD(TestMethod5)
		{
			Solution sln;
			n = 3, s1 = "pzd", s2 = "wgp", evil = "sd";
			auto res = sln.findGoodStrings(n, s1, s2, evil);
			AssertEx(4219, res);
		}
		TEST_METHOD(TestMethod94)
		{
			Solution sln;
			n = 93, s1 = "kazxkmmctdgtrplfggliycskmbfzjkrsthahcrxaaylpdykqfyejwteexytvxgjrbviconioomfpznawsseisfcpfkuvx",
				s2 = "lajtokckoizywvirjhccouuhjkkshdtzchzmiccujzpeqzcvfekdqjgrbkzrwfnfwhyvzrrrakiausbleeimmthaqqouh", evil = "kpvphwnkrtxuiuhb";
			auto res = sln.findGoodStrings(n, s1, s2, evil);
			AssertEx(982374807, res);
		}
	};

	TEST_CLASS(LC3490)
	{
	public:
		//【动态规划 数位dp】3490. 统计美丽整数的数目|2502
		template<class ELE, class ResultType, class MaskType = long long>
		class IDoForDigitDPMap {
		public:
			virtual void OnEnumOtherBit(unordered_map<MaskType, ResultType>& dp, const unordered_map<MaskType, ResultType> vPre, ELE curValue) = 0;
			virtual void OnEnumFirstBit(unordered_map<MaskType, ResultType>& vPre, const ELE curValue) = 0;
			virtual void OnSum(int iBit, const unordered_map<MaskType, ResultType>& dp) = 0;
		};
		template<class ELE, class ResultType, class MaskType = long long>
		class CDigitDPFullMap
		{
		public:
			void Init(int iMaxBit, ELE firstMin, ELE otherMin, ELE maxEle, IDoForDigitDPMap<ELE, ResultType, MaskType>& forDo) {
				for (ELE ele = firstMin; ele <= maxEle; ele++) {
					forDo.OnEnumFirstBit(m_pre, ele);
				}
				forDo.OnSum(0, m_pre);
				for (int i = 1; i < iMaxBit; i++) {
					unordered_map<MaskType, ResultType> cur;
					for (ELE ele = otherMin; ele <= maxEle; ele++) {
						forDo.OnEnumOtherBit(cur, m_pre, ele);
					}
					m_pre.swap(cur);
					forDo.OnSum(i, m_pre);
				}
			}
		protected:
			unordered_map<MaskType, ResultType> m_pre;
		};
		template<class ELE, class ResultType, class MaskType = long long>
		class CDigitDPMap
		{
		public:
			void Init(int iMaxBit, ELE firstMin, ELE otherMin, ELE  maxEle, ELE* p, IDoForDigitDPMap<ELE, ResultType, MaskType>& forDo) {
				m_pre.resize(2);
				for (ELE ele = firstMin; ele < p[0]; ele++) {
					forDo.OnEnumFirstBit(m_pre[0], ele);
				}
				forDo.OnEnumFirstBit(m_pre[1], p[0]);
				for (int i = 1; i < iMaxBit; i++) {
					vector<unordered_map<MaskType, ResultType>> cur(2);
					for (ELE ele = otherMin; ele <= maxEle; ele++) {//前驱状态不是上边界
						forDo.OnEnumOtherBit(cur[0], m_pre[0], ele);
					}
					//前驱状态是上边界
					for (ELE ele = otherMin; ele < p[i]; ele++) {
						forDo.OnEnumOtherBit(cur[0], m_pre[1], ele);
					}
					forDo.OnEnumOtherBit(cur[1], m_pre[1], p[i]);
					m_pre.swap(cur);
				}
				forDo.OnSum(iMaxBit - 1, m_pre[0]);
				forDo.OnSum(iMaxBit - 1, m_pre[1]);
			}
		protected:
			vector<unordered_map<MaskType, ResultType>> m_pre;
		};

		template<class ELE = char, class ResultType = int, class MaskType = long long>
		class CMyDoForDigitDPMap : public IDoForDigitDPMap<ELE, ResultType, MaskType>
		{
		public:
			virtual void OnEnumOtherBit(unordered_map<MaskType, ResultType>& dp, const unordered_map<MaskType, ResultType> vPre, ELE curValue) {
				const int curval = curValue - '0';
				for (const auto& [m, val] : vPre) {
					const int mul = m / m_iUnit * curval;
					const int sum = m % m_iUnit + curval;
					dp[Mask(mul, sum)] += val;
				}
			}
			virtual void OnEnumFirstBit(unordered_map<MaskType, ResultType>& vPre, const ELE curValue) {
				const int val = curValue - '0';
				vPre[Mask(val, val)]++;
			}
			virtual void OnSum(int iBit, const unordered_map<MaskType, ResultType>& dp) {
				int ans = 0;
				for (const auto& [m, val] : dp) {
					const int mul = m / m_iUnit;
					const int sum = m % m_iUnit;
					if ((0 == sum) || (0 != mul % sum)) { continue; }
					ans += val;
				}
				m_res.emplace_back(ans);
			}
			long long Mask(int mul, int sum) {
				return (long long)m_iUnit * mul + sum;
			}
			vector<int> m_res;
			const int m_iUnit = 1e9;
		};
		class Solution {
		public:
			int beautifulNumbers(int l, int r) {
				CMyDoForDigitDPMap dpr, dpl, dpfull;
				CDigitDPMap<char, int>  dr, dl;
				CDigitDPFullMap<char, int> dfull;
				string str1 = to_string(l - 1);
				string str2 = to_string(r);
				dr.Init(str2.length(), '1', '0', '9', str2.data(), dpr);
				dl.Init(str1.length(), '1', '0', '9', str1.data(), dpl);
				int ans = dpr.m_res[0] + dpr.m_res[1] - dpl.m_res[0] - dpl.m_res[1];
				if (str1.length() == str2.length()) { return ans; }
				dfull.Init(str2.length() - 1, '1', '0', '9', dpfull);
				for (int i = str1.length() - 1; i < dpfull.m_res.size(); i++) {
					ans += dpfull.m_res[i];
				}
				return ans;
			}
		};
		TEST_METHOD(TestMethod11)
		{
			auto res = Solution().beautifulNumbers(10, 20);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().beautifulNumbers(1, 15);
			AssertEx(10, res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().beautifulNumbers(1, 9);
			AssertEx(9, res);
		}
		TEST_METHOD(TestMethod14)
		{
			auto res = Solution().beautifulNumbers(3253, 298822441);
			AssertEx(196463489, res);
		}
		TEST_METHOD(TestMethod15)
		{
			auto res = Solution().beautifulNumbers(1, 1);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod16)
		{
			auto res = Solution().beautifulNumbers(5689, 522431457);
			AssertEx(350040194, res);
		}
		TEST_METHOD(TestMethod17)
		{
			auto res = Solution().beautifulNumbers(100, 100);
			AssertEx(1, res);
		}
	};
	TEST_CLASS(LC902)
	{
	public:
		//【数位dp】902最大为 N 的数字组合|1990	
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
		public:
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				if (!m_bVilid[cur]) { return; }
				dp[0] += vNext[0];
			}
			int m_iK;
			bool m_bVilid[10] = { false };
		};
		class Solution {
		public:
			int atMostNGivenDigitSet(vector<string>& digits, int n) {		
				string s = to_string(n);
				CCall<char, int> call;
				for (const auto& s : digits) {
					call.m_bVilid[s[0] - '0'] = true;
				}
				CUperrDP2<char, int> up(1, call, '1', '9','1');
				up.Init(s.c_str(), s.length());
				return up.Sum();
			}
		};

		vector<string> digits;
		int n;
		int res;
		TEST_METHOD(TestMethod11)
		{
			digits = { "1", "3", "5", "7" };
			int n = 100;
			res = Solution().atMostNGivenDigitSet(digits, n);
			AssertEx(20, res);
		}
		TEST_METHOD(TestMethod12)
		{
			digits = { "1", "4", "9" };
			int n = 1000000000;
			res = Solution().atMostNGivenDigitSet(digits, n);
			AssertEx(29523, res);
		}
		TEST_METHOD(TestMethod13)
		{
			digits = { "7" };
			int n = 8;
			res = Solution().atMostNGivenDigitSet(digits, n);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod01)
		{
			digits = { "2", "4", "6" };
			int n = 27;
			res = Solution().atMostNGivenDigitSet(digits, n);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod02)
		{
			digits = { "2", "4", "6" };
			int n = 31;
			res = Solution().atMostNGivenDigitSet(digits, n);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod03)
		{
			digits = { "5", "7", "8" };
			int n = 59;
			res = Solution().atMostNGivenDigitSet(digits, n);
			AssertEx(6, res);
		}
	};
	TEST_CLASS(LC3704)
	{
	public:
		//【数位dp】3704. 统计和为 N 的无零数对|2419
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
		public:
			CCall(const string& str):m_str(str){
			}	
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp) 
			{
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				int a = curValue - '0';
				for (int carryCur = 0;carryCur < 2;carryCur++) {
					for (int m = 0;m < 8;m++) {
						const bool carryNext = m & 4;
						int b = (carryCur ? 10 : 0) + m_str[n] - '0' - a - carryNext;
						if ((b < 0)||(b>9)) { continue; }
						if ((m & 2) && a) { continue; }
						if ((m & 1) && b) { continue; }
						const int m1 = 4 * carryCur + 2 * (0 == a) + (0 == b);
						dp[m1] += vNext[m];
					}
				}
			}
			string m_str;
		};
		class Solution {
		public:
			long long countNoZeroPairs(long long n) {
				string s = to_string(n);
				CCall<char, long long> call(s);
				CUperrDP<char, long long> dp(8, call, '0', '9');
				dp.Init(s.c_str(), s.length());
				long long ans = dp.Sum(0, 3) ;
				if (-1 == s.find("0")) { ans -= 2; }
				return ans ;
			}
		};
	
		TEST_METHOD(TestMethod11)
		{
			auto res = Solution().countNoZeroPairs(2);
			AssertEx(1LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().countNoZeroPairs(3);
			AssertEx(2LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().countNoZeroPairs(11);
			AssertEx(8LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			auto res = Solution().countNoZeroPairs(10);
			AssertEx(9LL, res);
		}
	};
	TEST_CLASS(LC3747)
	{//【数位dp】3747. 统计移除零后不同整数的数目|分数未知

		template<class ELE, class ResultType>
		class IUpperDPCall
		{
		public:
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount) = 0;
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp) = 0;
		};

		template<class ELE, class ResultType>
		class CUperrDP
		{
		public:
			CUperrDP(int iCustomStatusCount, IUpperDPCall<ELE, ResultType>& call, ELE minEle, ELE maxEle)
				:m_iCustomStatusCount(iCustomStatusCount), m_call(call), m_minEle(minEle), m_maxEle(maxEle)
			{
			}
			void Init(const ELE* pHigh, int iEleCount)
			{
				m_vDP.assign(iEleCount + 1, vector<ResultType>(m_iCustomStatusCount));
				m_vDpUpper = m_vDP;
				m_call.OnInitEnd(m_vDP.back(), m_vDpUpper.back());
				//预处理增加的一位
				for (int i = iEleCount - 1; i > 0; i--) {
					m_call.OnEnum(i, m_vDpUpper[i], m_vDpUpper[i + 1], pHigh[i], m_iCustomStatusCount);
					for (auto j = m_minEle; j < pHigh[i]; j++) {
						m_call.OnEnum(i, m_vDpUpper[i], m_vDP[i + 1], j, m_iCustomStatusCount);
					}
					for (auto j = m_minEle; j <= m_maxEle; j++) {
						m_call.OnEnum(i, m_vDP[i], m_vDP[i + 1], j, m_iCustomStatusCount);
					}
				}
				m_call.OnEnum(0, m_vDpUpper[0], m_vDpUpper[1], pHigh[0], m_iCustomStatusCount);
				for (auto j = m_minEle; j < pHigh[0]; j++) {
					m_call.OnEnum(0, m_vDP[0], m_vDP[1], j, m_iCustomStatusCount);
				}
			}
			ResultType Sum(int iMinCustomStatu, int iMaxCustomStatu) {
				ResultType ret = 0;
				for (int i = iMinCustomStatu; i <= iMaxCustomStatu; i++) {
					ret += m_vDP[0][i] + m_vDpUpper[0][i];
				}
				return ret;
			}
			ResultType Sum() {
				return Sum(0, m_iCustomStatusCount - 1);
			}
			vector<vector<ResultType>> m_vDP, m_vDpUpper;
			const ELE m_minEle, m_maxEle;
		protected:
			const int m_iCustomStatusCount;
			IUpperDPCall<ELE, ResultType>& m_call;
		};


		template<class ELE, class ResultType>
		class CMyUperrDP :public CUperrDP<ELE, ResultType>
		{
		public:
			using CUperrDP<ELE, ResultType>::CUperrDP;
			ResultType SumEx() {
				ResultType ret = 0;
				for (int j = 0; j + 1 < CUperrDP<ELE, ResultType>::m_vDP.size(); j++)
				{
					ret += CUperrDP<ELE, ResultType>::m_vDP[j][0];
				}
				ret += CUperrDP<ELE, ResultType>::m_vDpUpper[0][0];
				return ret;
			}
		};

		template<class ELE = char, class ResultType = long long>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount) {
				if ('0' == curValue) { return; }
				dp[0] += vNext[0];
			}
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp) {
				dp[0] = upDp[0] = 1;
			}
		};

		class Solution {
		public:
			long long countDistinct(long long n) {
				CCall<> call;
				CMyUperrDP<char, long long> up(1, call, '0', '9');
				string str = to_string(n);
				up.Init(str.c_str(), str.length());
				return up.SumEx();
			}
		};
	public:
		long long n;

		TEST_METHOD(TestMethod11)
		{
			auto res = Solution().countDistinct(10);
			AssertEx(9LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().countDistinct(3);
			AssertEx(3LL, res);
		}

		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().countDistinct(20);
			AssertEx(18LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			auto res = Solution().countDistinct(11);
			AssertEx(10LL, res);
		}
	};
}

namespace DigitDPLG
{
	TEST_CLASS(P9362)
	{
		//【数学 进制 数位DP】P9362 [ICPC 2022 Xi‘an R] Find Maximum|普及+
		template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
		public:		
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				dp[0] = upDp[0] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				for (int i = cur;i < iCustomStatusCount;i++) {					
					dp[i] += vNext[i-cur];
				}
			}
			vector<vector<int>> m_vTo;
			int m_iK;
		};
		class Solution {
		public:
			vector<int> Ans(vector<pair<unsigned long long, unsigned long long>>& LR) {
				vector<int> ans;
				for (const auto& [l, r] : LR) {
					ans.emplace_back(Do(l, r)+1);
				}
				return ans;
			}
			int Do(unsigned long long L, unsigned long long R) {
				CCall<char, long long> call;
				CUperrDP2<char, long long> dp1(3 * M + 1, call, '0', '2','1'), dp2(3 * M + 1, call, '0', '2','1');
				string str1 = To3(L);
				string str2 = To3(R);
				dp1.Init(str1.c_str(), str1.length());
				dp2.Init(str2.c_str(), str2.length());
				int y3 = str1.length()-1;
				for (const auto& ch : str1) {
					y3 += ch - '0';
				}
				vector<long long> cnt(4 * M);
				cnt[y3]++;
				for (int i = 0; i < str1.size();i++)
				{
					for (int j = M * 3; j >= 0;j--)
					{		
						cnt[str1.size() - 1 - i + j] -= dp1.m_vFirstDP[i][j];
					}
				}
				for (int i = 0; i < str2.size();i++)
				{
					for (int j = M * 3; j >= 0;j--)
					{
						cnt[str2.size() - 1 - i + j] += dp2.m_vFirstDP[i][j];
					}
				}
				for (int j = cnt.size()-1; j >= 0;j--)
				{
					if (cnt[j] > 0) { return j; }
				}
				return 0;
			}
			string To3(unsigned long long L) {
				string str;
				while (L) {
					str += ('0' + L % 3);
					L /= 3;
				}
				if ("" == str) { str = "0"; }
				return string(str.rbegin(), str.rend());
			}
			vector< unsigned long long> m_unit;
			vector<int> m_v;
			const int M = 41;
		};
	public:
		vector<pair<unsigned long long, unsigned long long>> LR;
		TEST_METHOD(TestMethod01)
		{
			LR = { {2,3},{2,4},{9,10},{9,9} };
			auto res = Solution().Ans(LR);
			AssertV({ 3,4,5,4 }, res);
		}
	};
}